거품 정렬

거품 정렬은 서로 인접한 두 원소의 크기를 비교하여 순서가 잘못된 경우 교환하는 방식을 반복하여 정렬을 수행하는 간단한 정렬 알고리즘이다. 비교 정렬에 속하며, 정렬 과정에서 값이 큰 원소가 마치 물속의 거품처럼 한 칸씩 위로 올라가는 모습을 보여 거품 정렬이라는 이름이 붙었다.

이 알고리즘은 시간 복잡도 측면에서 효율적이지 않다. 최선의 경우, 즉 이미 정렬된 배열에 대해서는 O(n)의 시간이 소요되지만, 평균과 최악의 경우 O(n²)의 시간이 걸린다. 그러나 공간 복잡도는 O(1)로, 추가적인 메모리 공간을 거의 사용하지 않는 제자리 정렬의 특성을 가진다. 또한 동일한 값을 가진 원소들의 상대적 순서를 유지하는 안정 정렬이다.

구현이 매우 직관적이고 단순하여 알고리즘 학습 시 초기에 접하는 대표적인 정렬 방법 중 하나이다. 그러나 선택 정렬이나 삽입 정렬과 같은 다른 단순 정렬 알고리즘에 비해 실제 성능이 떨어지는 경우가 많아, 교육 목적 외의 실무에서는 거의 사용되지 않는다.

거품 정렬의 기본 원리는 인접한 두 원소를 비교하여 순서가 잘못된 경우 교환하는 작업을 반복하는 것이다. 이 과정은 배열의 처음부터 끝까지 진행되며, 각 반복이 완료될 때마다 가장 큰 원소가 올바른 위치로 이동하게 된다. 이러한 방식은 마치 물속에서 거품이 떠오르는 것과 비슷하여 알고리즘의 이름이 붙여졌다.

구체적으로, 거품 정렬은 배열의 첫 번째 원소와 두 번째 원소를 비교하여 첫 번째 원소가 더 크면 두 원소의 위치를 교환한다. 그 다음, 두 번째 원소와 세 번째 원소를 같은 방식으로 비교하고, 이 과정을 배열의 마지막 원소까지 계속한다. 이렇게 배열의 끝까지 한 번 순회하는 것을 1회전(pass)이라고 한다.

1회전이 끝나면 가장 큰 원소가 배열의 마지막 자리로 이동하게 된다. 다음 회전에서는 마지막 원소를 제외한 나머지 원소들에 대해 동일한 비교 및 교환 과정을 반복한다. 따라서 각 회전이 끝날 때마다 정렬되지 않은 부분에서 가장 큰 원소가 그 부분의 끝으로 이동하며, 정렬된 영역이 점차 확장된다.

이 알고리즘은 비교 정렬이며, 안정 정렬의 특성을 가진다. 원소의 이동은 인접한 쌍끼리의 교환을 통해서만 이루어지기 때문에, 같은 값을 가진 원소들의 상대적 순서가 정렬 과정에서 유지된다.

거품 정렬의 기본적인 의사 코드는 다음과 같다. 이 코드는 주어진 배열의 요소를 인접한 두 요소를 비교하여 순서가 잘못된 경우 교환하는 과정을 반복한다. 외부 루프는 전체 정렬 과정을 통제하며, 내부 루프는 각 패스에서 실제 비교와 교환을 수행한다.

의사 코드의 핵심은 이중 루프 구조이다. 외부 루프는 배열의 길이 n만큼 반복한다. 각 외부 루프의 반복(패스)이 끝날 때마다 가장 큰 요소가 배열의 끝자리로 이동하게 되어, 다음 패스에서는 정렬되지 않은 부분의 길이가 하나씩 줄어든다. 내부 루프는 현재 정렬되지 않은 부분을 순회하며 인접한 요소를 비교하고, 필요시 교환한다.

```

procedure bubbleSort(A : list of sortable items)

n := length(A)

for i from 0 to n-1 do

for j from 0 to n-i-2 do

if A[j] > A[j+1] then

swap(A[j], A[j+1])

end if

end for

end for

end procedure

```

이 기본적인 의사 코드는 최적화 없이 작성된 것이다. 실제 구현에서는 플래그를 이용한 조기 종료나 코크테일 셰이커 정렬과 같은 변형을 적용하여 성능을 개선할 수 있다. 위 코드는 안정 정렬 특성을 가지며, 제자리 정렬 알고리즘으로 공간 복잡도가 낮다는 특징이 있다.

거품 정렬의 시간 복잡도는 입력 데이터의 초기 상태에 따라 크게 달라진다. 최선의 경우는 이미 정렬된 배열이 입력으로 주어질 때이다. 이 경우 알고리즘은 첫 번째 패스에서 한 번도 교환하지 않고 종료할 수 있으므로, 시간 복잡도는 O(n)이 된다. 이는 선형 시간에 해당한다.

반면, 평균적인 경우와 최악의 경우 시간 복잡도는 O(n²)이다. 최악의 경우는 배열이 역순으로 정렬되어 있을 때 발생한다. 이 경우 알고리즘은 각 패스마다 인접한 요소들을 비교하고 필요한 경우 교환하는 과정을 반복하며, n개의 요소에 대해 대략 n(n-1)/2번의 비교 연산을 수행하게 된다. 이는 이차 시간 복잡도를 의미한다.

이러한 높은 시간 복잡도로 인해 거품 정렬은 교육 목적이나 매우 작은 데이터셋을 제외하고는 실용적인 정렬 알고리즘으로 사용되지 않는다. 대규모 데이터를 정렬할 때는 퀵 정렬, 병합 정렬, 힙 정렬과 같은 더 효율적인 알고리즘이 선호된다.

거품 정렬의 공간 복잡도는 O(1)이다. 이는 알고리즘이 입력 데이터 외에 추가적인 메모리 공간을 거의 사용하지 않는다는 것을 의미한다. 정렬 과정에서 두 원소의 값을 교환하기 위해 사용하는 임시 변수와 같은 상수 크기의 공간만 필요로 하므로, 제자리 정렬 알고리즘으로 분류된다.

이러한 낮은 공간 복잡도는 거품 정렬의 주요 장점 중 하나이다. 메모리 사용량이 매우 적기 때문에, 제한된 메모리 환경에서도 사용하기에 적합하다. 이는 선택 정렬이나 삽입 정렬과 같은 다른 단순한 제자리 정렬 알고리즘들과 공통된 특징이다.

따라서 거품 정렬은 시간 효율성은 떨어질 수 있으나, 공간 효율성 측면에서는 매우 우수한 알고리즘이다. 이 특성은 대용량 데이터를 처리해야 하지만 메모리 자원이 귀한 임베디드 시스템이나 초기 컴퓨팅 환경에서 일정한 장점으로 작용했다.

거품 정렬의 가장 큰 장점은 알고리즘의 개념과 구현이 매우 단순하고 직관적이라는 점이다. 이로 인해 정렬 알고리즘을 처음 배우는 교육용 목적으로 자주 활용된다. 또한, 제자리 정렬 알고리즘이기 때문에 추가적인 메모리 공간을 거의 사용하지 않으며, 안정 정렬의 특성을 가져 동일한 키 값을 가진 원소들의 상대적 순서가 유지된다.

반면, 거품 정렬의 가장 큰 단점은 시간 복잡도가 매우 비효율적이라는 것이다. 평균 및 최악의 경우 시간 복잡도가 O(n²)에 달해, 데이터의 양이 많아질수록 성능이 급격히 저하된다. 이는 현실적인 대규모 데이터 정렬에는 거의 사용되지 않는 주된 이유이다. 삽입 정렬과 같은 다른 단순 정렬 알고리즘과 비교해도, 일반적으로 더 느린 성능을 보인다.

알고리즘의 동작 방식 상, 인접한 두 원소를 비교하고 필요시 교환하는 과정이 배열의 끝까지 반복되므로, 특히 정렬이 이미 어느 정도 되어 있는 경우에도 불필요한 비교 연산을 많이 수행할 수 있다. 이러한 비효율성 때문에 교육 목적 외의 실용적인 소프트웨어 개발에서는 퀵 정렬, 병합 정렬, 힙 정렬 등의 고성능 알고리즘이 선호된다.

거품 정렬 알고리즘은 다양한 프로그래밍 언어로 구현할 수 있다. 핵심은 인접한 두 원소를 비교하여 순서가 잘못된 경우 교환하는 과정을 반복하는 것이다. 아래는 C 언어로 작성된 기본적인 구현 예시이다. 이 함수는 정수 배열을 오름차순으로 정렬한다.

```c

void bubbleSort(int arr[], int n) {

for (int i = 0; i < n-1; i++) {

for (int j = 0; j < n-i-1; j++) {

if (arr[j] > arr[j+1]) {

// 두 원소 교환

int temp = arr[j];

arr[j] = arr[j+1];

arr[j+1] = temp;

}

}

}

}

```

이 코드에서 외부 루프는 전체 패스를 제어하며, 내부 루프는 각 패스에서 인접한 원소를 비교하고 교환한다. 각 패스가 끝나면 가장 큰 원소가 배열의 끝으로 이동하게 되어 내부 루프의 비교 범위가 점차 줄어든다. 이 기본 구현은 최적화되지 않았으며, 이미 정렬된 배열에 대해서도 불필요한 비교를 계속 수행한다. 플래그를 이용한 조기 종료나 코크테일 셰이커 정렬과 같은 변형 알고리즘을 적용하면 성능을 개선할 수 있다.

• 위키백과 - 정렬 알고리즘

• 위키백과 - 선택 정렬

• 위키백과 - 삽입 정렬

• 위키백과 - 합병 정렬

• 위키백과 - 퀵 정렬

• GeeksforGeeks - Bubble Sort

• Khan Academy - 버블 정렬 알고리즘